Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search
面向高效近似最近邻搜索的邻近图索引无损压缩
🧭 向量检索 · HNSW 图索引压缩
ISTI-CNR · eBay Inc. · University of Pisa
通过离线图置换制造结构局部性，用 SIMD 整数压缩器快速解压 HNSW 邻接表，压缩率最高 52.7% 且延迟近零损失
📌 工作参考价值（4 点）
- 电商/广告向量召回中 HNSW 内存吃紧时，先定位边存储占比：若向量已量化、图边成为主要开销，可对邻接表做离线节点重编号，再使用 Stream VByte 等 SIMD 整数压缩器，在线边解压边遍历，基本不损失延迟。
- 关键 trick 是离线图置换：人为让邻接表内的 ID 分布更集中，能显著提升整数压缩器的压缩率；业务上可直接对 item/user embedding 的 HNSW 索引做同样的重编号，无需改召回精度。
- 如果已经在用 PQ/Scalar quantization，此方法可叠加使用，进一步降低 HNSW 整体内存，缩小索引集群规模或支持更大规模向量库。
- 工程落地优先选 SIMD 友好的解压器（如 Stream VByte），避免复杂熵编码带来的分支和延迟；上线前需重点验证查询 P99/P999 延迟，并做无损压缩以避免召回质量回退。